##A POJ 1321
思路：这条题目给定棋盘，要求横竖不能放，按行数开始dfs，按列数循环，深搜进入下一层，本行测试完成后，直接进入下一行。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65//回溯法
#include <iostream>
#include <cstdio>
using namespace std;
//定义棋盘
char qipan[8][8];
//从行扫描，所以仅记录列数是否被占用，
bool col[8];
//m是需要填充的个数
//n是棋盘规模
//cur是当前已填充个数
int m,n;
int cur;
//r为行数，k代表已经填充的棋子数，cur代表方案数
void dfs(int r, int k)
{
if (k == m)
{
cur++;
return;
}
if (r > n)
{
return;
}
//若第i列没有放且qipan[r][i] == '#'，若不能填，直接进入下一次循环
for (int i = 0; i < n; i++)
{
if (!col[i] && qipan[r][i] == '#')
{
col[i] = 1;
dfs(r + 1, k + 1);
col[i] = 0;
}
}
//本行已经全部测试完成，直接进入下一行
dfs(r + 1, k);
}
int main(){
while (cin>>m>>n)
{
if (n == -1 && m == -1) break;
cur = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> qipan[i][j];
}
}
memset(col, false, sizeof(col));
dfs(0, 0);
cout << cur << endl;
}
return 0;
}
##B POJ 2251
3DBFS，扩展而已。水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
int L, R, C;
const int maxn = 32;
struct Node
{
int l, r, c;
int path;
//-1 = # 1 = . 2 = E
int own;
void assign(int x, int y, int z)
{
l = x; r = y; c = z;
path = -1;
own = 0;
}
}node[maxn][maxn][maxn];
queue<Node> Q;
int bfs()
{
Node temp;
while (!Q.empty())
{
temp = Q.front();
if (temp.own == 2)return temp.path;
for (int dl = -1; dl < 2; dl++)
for (int dr = -1; dr < 2; dr++)
for (int dc = -1; dc < 2; dc++)
{
int a[3] = { dl, dr, dc };
sort(a, a + 3);
if (!((a[0] == 0 && a[1] == 0) || (a[1] == 0 && a[2] == 0)))continue;
if (temp.l + dl > 0 && temp.l + dl <= L && temp.r + dr > 0 && temp.r + dr <= R && temp.c + dc > 0 && temp.c + dc <= C && node[temp.l + dl][temp.r + dr][temp.c + dc].own > 0 && node[temp.l + dl][temp.r + dr][temp.c + dc].path < 0)
{
node[temp.l + dl][temp.r + dr][temp.c + dc].path = node[temp.l][temp.r][temp.c].path + 1;
Q.push(node[temp.l + dl][temp.r + dr][temp.c + dc]);
}
}
Q.pop();
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> L >> R >> C)
{
if (L == 0 && R == 0 && C == 0)break;
while (!Q.empty())Q.pop();
string tmp;
for (int i = 1; i <= L; i++)
{
for (int j = 1; j <= R; j++)
{
cin >> tmp;
for (int k = 1; k <= C; k++)
{
node[i][j][k].assign(i, j, k);
switch (tmp[k - 1])
{
case '.':node[i][j][k].own = 1; break;
case 'S':node[i][j][k].own = 1; node[i][j][k].path = 0; Q.push(node[i][j][k]); break;
case 'E':node[i][j][k].own = 2; break;
}
}
}
}
int ans = bfs();
if (ans == 0)cout << "Trapped!\n";
else cout << "Escaped in " << ans << " minute(s).\n";
}
return 0;
}
##C POJ 3278
隐式bfs。水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 100001;
int N, K;
queue<int> Q;
int path[maxn];
int main()
{
cin >> N >> K;
memset(path, -1, sizeof(path));
path[N] = 0;
Q.push(N);
int temp;
while (!Q.empty())
{
temp = Q.front();
Q.pop();
if (temp == K) { cout << path[temp] << endl; }
if (temp > 0 && path[temp - 1] < 0)
{
Q.push(temp - 1);
path[temp - 1] = path[temp] + 1;
}
if (temp < 100000 && path[temp + 1] < 0)
{
Q.push(temp + 1);
path[temp + 1] = path[temp] + 1;
}
if (temp * 2 < maxn && path[temp * 2] < 0)
{
Q.push(temp * 2);
path[temp * 2] = path[temp] + 1;
}
}
return 0;
}
##D POJ 3279
值得注意的是第一行一旦确定后面行也确定。从这点出发的暴力运算量就可以AC1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110//显然每个位置只能为0或1，不可能为2
//而当第一行一旦确定，后面的m-1行也就确定
//因此只要穷举第一行的情况，1<<16的运算量，再选字典序最小即可
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int M, N;
int m[17][17];
int map[17][17];
int ans[17][17];
int minans[17][17];
int minp = (1 << 30);
int minv = (1 << 30);
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
void flip(int row, int col)
{
if (map[row][col] == 0)map[row][col] = 1;
else map[row][col] = 0;
for (int i = 0; i < 4; i++)
{
if (row + dx[i] < 0 || row + dx[i] > M - 1 || col + dy[i] < 0 || col + dy[i] > N - 1)continue;
if (map[row + dx[i]][col + dy[i]] == 0)map[row + dx[i]][col + dy[i]] = 1;
else map[row + dx[i]][col + dy[i]] = 0;
}
}
int main()
{
cin >> M >> N;
memset(m, -1, sizeof(m));
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
cin >> m[i][j];
}
bool fuck = false;
for (int i = 0; i < (1 << N); i++)
{
memset(ans, 0, sizeof(ans));
for (int x = 0; x < M; x++)
{
for (int y = 0; y < N; y++)
map[x][y] = m[x][y];
}
for (int j = 0; j < N; j++)
{
ans[0][j] = (i & (1 << j));
if (ans[0][j] > 0)
{
ans[0][j] = 1;
flip(0, j);
}
}
for (int j = 1; j < M; j++)
{
for (int k = 0; k < N; k++)
{
if (map[j - 1][k] == 1)
{
flip(j, k);
ans[j][k] = 1;
}
}
}
bool zz = true;
for (int j = 0; j < N; j++)
{
if (map[M - 1][j] == 1)
{
zz = false;
break;
}
}
if (zz)
{
fuck = true;
int p = 0;
for (int k = 0; k < M; k++)
for (int j = 0; j < N; j++)
{
p += ans[k][j];
}
if (p < minv || (p == minv && minp > i))
{
minv = p;
minp = i;
memcpy(minans, ans, sizeof(ans));
}
}
}
if (!fuck)cout << "IMPOSSIBLE\n";
else
{
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N - 1; j++)
{
cout << minans[i][j] << " ";
}
cout << minans[i][N - 1] << endl;
}
}
return 0;
}
##E POJ 1426
隐式bfs剪枝，从最高位1开始。利用数论的知识来优化就不会爆炸1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69//第一位必定为1 选最小的即可
//从最高位开始向后bfs，补0或1
//剪枝：对于完全剩余系0-n-1
//比如在第3位出现了k，而到第9位为0，结束
//那么我在第6位又出现k，显然到12位就会为0
//因此可以直接把又出现k的情况直接扔掉
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int N;
struct Node
{
int value;
int pos;
int store[205];
Node() {}
Node(int a) :pos(a), value(1) { memset(store, 0, sizeof(store)); store[a] = 1; }
Node(Node n, int p)
{
pos = n.pos + 1;
value = (n.value * 10 + p) % N;
memcpy(store, n.store, sizeof(store));
store[pos] = p;
}
void print()
{
for (int i = 1; i <= pos; i++)
{
cout << store[i];
}
cout << endl;
}
};
Node first;
queue<Node> Q;
int visited[205];
int main()
{
while (cin >> N && N > 0)
{
memset(visited, 0, sizeof(visited));
while (!Q.empty())
{
Q.pop();
}
first = Node(1);
Q.push(first);
while (!Q.empty())
{
first = Q.front();
Q.pop();
if (visited[first.value] == 1)continue;
else visited[first.value] = 1;
if (first.value == 0)
{
first.print();
break;
}
Q.push(Node(first, 0));
Q.push(Node(first, 1));
}
}
return 0;
}
##F POJ 3126
注意素数的判别不要弄错，小于等于根号n1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103//注意判断素数那里小于等于根号i
#include<iostream>
#include<set>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int M;
bool prime[10005];
int path[10005];
queue<int> Q;
void primebuild()
{
memset(prime, 0, sizeof(prime));
for (int i = 1001; i < 10000; i++)
{
int temp = floor(sqrt(1.0*i) + 0.5);
bool fuck = true;
for (int j = 2; j <= temp; j++)
{
if (i % j == 0)
{
fuck = false;
break;
}
}
prime[i] = fuck;
}
}
int bfs(int a, int b)
{
memset(path, -1, sizeof(path));
while (!Q.empty())
{
Q.pop();
}
path[a] = 0;
Q.push(a);
int first;
while (!Q.empty())
{
first = Q.front();
Q.pop();
if (first == b)return path[first];
int p = first % 1000;
for (int i = 1; i < 10; i++)
{
p += 1000;
if (path[p] < 0 && prime[p])
{
Q.push(p);
path[p] = path[first] + 1;
}
}
p = (first / 1000) * 1000 + (first % 100);
for (int i = 0; i < 10; i++)
{
if (path[p] < 0 && prime[p])
{
Q.push(p);
path[p] = path[first] + 1;
}
p += 100;
}
p = first - (first % 100) + (first % 10);
for (int i = 0; i < 10; i++)
{
if (path[p] < 0 && prime[p])
{
Q.push(p);
path[p] = path[first] + 1;
}
p += 10;
}
p = first - (first % 10);
for (int i = 0; i < 10; i++)
{
if (path[p] < 0 && prime[p])
{
Q.push(p);
path[p] = path[first] + 1;
}
p++;
}
}
return -1;
}
int main()
{
primebuild();
cin >> M;
while (M--)
{
int a, b;
cin >> a >> b;
cout << bfs(a, b) << endl;
}
return 0;
}
##G POJ 3087
模拟题，注意某一状态第二次出现时剪枝。水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55//纯模拟题，注意两副牌重复交叉一定次数一定会循环到开始
#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int M, C;
string a, b, c;
map<string, int> mm;
string change()
{
string ret = "";
for (int i = 0; i < (C << 1); i++)
{
if (i & 1) ret += a[i>>1];
else ret += b[i>>1];
}
a = ret.substr(0, C);
b = ret.substr(C, C);
return ret;
}
int main()
{
cin >> M;
for (int kase = 0; kase < M; kase++)
{
mm.clear();
cin >> C >> a >> b >> c;
cout << kase + 1 << " ";
int ans = 0;
while (true)
{
string temp = change();
ans++;
if (temp == c)break;
else
{
if (mm[temp] == 1)
{
ans = -1;
break;
}
else
{
mm[temp] = 1;
}
}
}
cout << ans << endl;
}
return 0;
}
##H POJ 3414
细节上别弄错。bfs水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125//类的构造函数的形参类型为该类必须用引用
//注意set放结构体的时候必须要重载<
#include<iostream>
#include<queue>
#include<set>
#include<string>
using namespace std;
int a, b, c;
struct State
{
int la, lb;
bool ok() { if (la == c || lb == c)return true; return false; }
int path;
string way;
State() :path(-1), la(0), lb(0), way("") {}
};
struct Node
{
int la, lb;
Node(State a):la(a.la), lb(a.lb) {}
};
bool operator < (Node a, Node b)
{
if (a.la != b.la)return a.la < b.la;
else return a.lb < b.lb;
}
set<Node> S;
queue<State> Q;
int main()
{
cin >> a >> b >> c;
State first;
first.path++;
Q.push(first);
bool fuck = false;
while (!Q.empty())
{
first = Q.front();
Q.pop();
Node node(first);
if (S.count(node))continue;
else S.insert(node);
if (first.ok())
{
cout << first.path << endl;
cout << first.way;
fuck = true;
break;
}
else
{
first.path++;
State temp = first;
if (first.la < a)
{
temp.way += "FILL(1)\n";
temp.la = a;
Q.push(temp);
}
temp = first;
if (first.lb < b)
{
temp.way += "FILL(2)\n";
temp.lb = b;
Q.push(temp);
}
temp = first;
if (first.la > 0)
{
temp.way += "DROP(1)\n";
temp.la = 0;
Q.push(temp);
}
temp = first;
if (first.lb > 0)
{
temp.way += "DROP(2)\n";
temp.lb = 0;
Q.push(temp);
}
temp = first;
if (first.la < a && first.lb > 0)
{
temp.way += "POUR(2,1)\n";
int cc = a - first.la;
if (cc > first.lb)
{
temp.la += first.lb;
temp.lb = 0;
}
else
{
temp.lb -= cc;
temp.la = a;
}
Q.push(temp);
}
temp = first;
if (first.lb < b && first.la > 0)
{
temp.way += "POUR(1,2)\n";
int cc = b - first.lb;
if (cc > first.la)
{
temp.lb += first.la;
temp.la = 0;
}
else
{
temp.la -= cc;
temp.lb = b;
}
Q.push(temp);
}
}
}
if (!fuck) cout << "impossible" << endl;
return 0;
}
##I FZU 2150
dfs穷举组合数+bfs。注意笔误1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127//dfs穷举组合数+bfs暴力
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
int map[12][12];
int grass[12][12];
int T, n, m;
int px[105], py[105];
int tot;
int fire[3];
int ans;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int visited[12][12];
struct Node
{
int x, y;
int path;
Node() {}
Node(int x, int y, int path) :x(x), y(y), path(path) {}
};
queue<Node> Q;
void dfs(int cur, int num)
{
if (cur == 2)
{
memcpy(grass, map, sizeof(map));
memset(visited, 0, sizeof(visited));
int t = -1;
Node t1 = Node(px[fire[0]], py[fire[0]], 0), t2 = Node(px[fire[1]], py[fire[1]], 0);
Q.push(t1);
Q.push(t2);
while (!Q.empty())
{
Node temp = Q.front();
Q.pop();
if (grass[temp.x][temp.y] == 0)continue;
else
{
t = max(t, temp.path);
grass[temp.x][temp.y] = 0;
for (int i = 0; i < 4; i++)
{
if (temp.x + dx[i] < 0 || temp.x + dx[i] > n - 1)continue;
if (temp.y + dy[i] < 0 || temp.y + dy[i] > m - 1)continue;
if (visited[temp.x + dx[i]][temp.y + dy[i]] == 1)continue;
Q.push(Node(temp.x + dx[i], temp.y + dy[i], temp.path + 1));
visited[temp.x + dx[i]][temp.y + dy[i]] = 1;
}
}
}
bool fuck = true;
for (int i = 0; i < n; i++)
{
bool cc = true;
for (int j = 0; j < m; j++)
{
if (grass[i][j] == 1)
{
cc = false;
break;
}
}
if (!cc)
{
fuck = false;
break;
}
}
if (fuck)
{
ans = min(ans, t);
}
}
else
{
for (int i = num; i < tot; i++)
{
fire[cur] = i;
dfs(cur + 1, i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> T;
for (int kase = 0; kase < T; kase++)
{
tot = 0;
ans = (1 << 30);
memset(map, 0, sizeof(map));
memset(px, -1, sizeof(px));
memset(py, -1, sizeof(py));
cin >> n >> m;
char chTmp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> chTmp;
if (chTmp == '#')
{
map[i][j] = 1;
px[tot] = i;
py[tot] = j;
tot++;
}
else
map[i][j] = 0;
}
cin.ignore();
}
dfs(0, 0);
if (ans == (1 << 30))ans = -1;
cout << "Case " << kase + 1 << ": " << ans << endl;
}
return 0;
}
##J UVA 11624
注意状态的先后变化。bfs水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int T;
int R, C;
int fr, fc;
int map[1005][1005];
int visited[1005][1005];
const int dr[] = { 0, 1, 0, -1 };
const int dc[] = { 1, 0, -1, 0 };
struct Node
{
int row, col;
int path;
bool fire;
Node() {}
Node(int row, int col, int path, bool fire) :row(row), col(col), path(path), fire(fire) {}
};
queue<Node> Q;
int main()
{
cin >> T;
while (T--)
{
while (!Q.empty())
{
Q.pop();
}
memset(map, -1, sizeof(map));
memset(visited, 0, sizeof(visited));
cin >> R >> C;
char chTmp;
for (int i = 1; i <= R; i++)
{
for (int j = 1; j <= C; j++)
{
cin >> chTmp;
if (chTmp == '#')
{
map[i][j] = -1;
}
else
{
if (chTmp == '.')
{
map[i][j] = 1;
}
else
{
if (chTmp == 'F')
{
map[i][j] = -2;
Q.push(Node(i, j, -1, true));
}
else
{
map[i][j] = 1;
fr = i;
fc = j;
}
}
}
}
cin.ignore();
}
Q.push(Node(fr, fc, 0, false));
bool fuck = true;
Node first;
while (!Q.empty())
{
first = Q.front();
Q.pop();
if (!first.fire)
{
for (int i = 0; i < 4; i++)
{
if (first.row + dr[i] < 1 || first.row + dr[i] > R || first.col + dc[i] < 1 || first.col + dc[i] > C)
{
fuck = false;
cout << first.path + 1 << endl;
break;
}
else
{
if (visited[first.row + dr[i]][first.col + dc[i]] == 0 && map[first.row + dr[i]][first.col + dc[i]] > 0)
{
visited[first.row + dr[i]][first.col + dc[i]] = 1;
Q.push(Node(first.row + dr[i], first.col + dc[i], first.path + 1, false));
}
}
}
if (!fuck)break;
}
else
{
for (int i = 0; i < 4; i++)
{
if (first.row + dr[i] < 1 || first.row + dr[i] > R || first.col + dc[i] < 1 || first.col + dc[i] > C)continue;
if (map[first.row + dr[i]][first.col + dc[i]] > 0 && visited[first.row + dr[i]][first.col + dc[i]] == 0)
{
Q.push(Node(first.row + dr[i], first.col + dc[i], -1, true));
map[first.row + dr[i]][first.col + dc[i]] = -2;
visited[first.row + dr[i]][first.col + dc[i]] = 1;
}
}
}
}
if (fuck)cout << "IMPOSSIBLE" << endl;
}
return 0;
}
##K POJ 3984
本专题最简单的水题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include<iostream>
#include<string>
#include<queue>
using namespace std;
int map[5][5];
int visited[5][5];
const int dr[] = { -1, 0, 1, 0 };
const int dc[] = { 0, -1, 0, 1 };
struct Node
{
int row, col;
int path;
string way;
Node(int row, int col, int path) :row(row), col(col), path(path) { way = ""; }
};
queue<Node> Q;
int main()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cin >> map[i][j];
Node first = Node(0, 0, 0);
first.way = "(0, 0)\n";
visited[0][0] = 1;
Q.push(first);
while (!Q.empty())
{
first = Q.front(); Q.pop();
if (first.row == 4 && first.col == 4)
{
cout << first.way;
break;
}
else
{
for (int i = 0; i < 4; i++)
{
if (first.row + dr[i] < 0 || first.row + dr[i] > 4 || first.col + dc[i] < 0 || first.col + dc[i] > 4)
{
continue;
}
else
{
if (map[first.row + dr[i]][first.col + dc[i]] == 0 && visited[first.row + dr[i]][first.col + dc[i]] == 0)
{
Node temp = first;
temp.row += dr[i];
temp.col += dc[i];
temp.path++;
temp.way += "(";
temp.way += first.row + dr[i] + 48;
temp.way += ", ";
temp.way += first.col + dc[i] + 48;
temp.way += ")\n";
Q.push(temp);
visited[first.row + dr[i]][first.col + dc[i]] = 1;
}
}
}
}
}
return 0;
}
##L HDU 1241
紫书例题，八连通图。水题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 105;
const int dr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int ans;
int r, c;
int map[maxn][maxn];
int visited[maxn][maxn];
void dfs(int row, int col);
int main()
{
char chTmp;
while (cin >> r >> c)
{
if (r == 0)break;
ans = 0;
memset(map, 0, sizeof(map));
memset(visited, 0, sizeof(map));
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
cin >> chTmp;
if (chTmp == '@')
map[i][j] = 1;
}
cin.ignore();
}
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
if (map[i][j] == 1 && visited[i][j] == 0)
{
dfs(i, j);
ans++;
}
}
}
cout << ans << endl;
}
return 0;
}
void dfs(int row, int col)
{
visited[row][col] = 1;
for (int i = 0; i < 8; i++)
{
if (row + dr[i] < 1 || row + dr[i] > r || col + dc[i] < 1 || col + dc[i] > c)continue;
if (map[row + dr[i]][col + dc[i]] == 1 && visited[row + dr[i]][col + dc[i]] == 0)
{
dfs(row + dr[i], col + dc[i]);
}
}
}
##M HDU 1495
和上面某题极其相似。水题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102#include<iostream>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
int s, n, m;
struct Node
{
int a, b, c;
int path;
Node(int a, int b, int c, int path) :a(a), b(b), c(c), path(path) {}
};
struct State
{
int a, b, c;
State() {}
State(Node x) :a(x.a), b(x.b), c(x.c) {}
};
bool operator < (const State& x, const State& y)
{
if (x.a != y.a) return x.a < y.a;
else
{
if (x.b != y.b) return x.b < y.b;
else return x.c < y.c;
}
}
set<State> S;
queue<Node> Q;
int main()
{
while (cin >> s >> n >> m)
{
while (!Q.empty())
{
Q.pop();
}
S.clear();
if (s == 0)break;
Node first = Node(s, 0, 0, 0);
State temp;
Q.push(first);
bool fuck = true;
if (s % 2 == 0)
while (!Q.empty())
{
first = Q.front(); Q.pop();
temp = State(first);
int pp[3] = { first.a, first.b, first.c };
sort(pp, pp + 3);
if (pp[1] == s / 2 && pp[2] == s / 2)
{
cout << first.path << endl;
fuck = false;
break;
}
if (S.count(temp) == 1)
{
continue;
}
else
{
S.insert(temp);
if (first.a > 0)
{
if (first.b < n)
{
Q.push(Node(max(0, first.a - n + first.b), min(n, first.b + first.a), first.c, first.path + 1));
}
if (first.c < n)
{
Q.push(Node(max(0, first.a - m + first.c), first.b, min(m, first.c + first.a), first.path + 1));
}
}
if (first.b > 0)
{
Q.push(Node(first.a + first.b, 0, first.c, first.path + 1));
if (first.c < m)
{
Q.push(Node(first.a, max(0, first.b - m + first.c), min(m, first.c + first.b), first.path + 1));
}
}
if (first.c > 0)
{
Q.push(Node(first.a + first.c, first.b, 0, first.path + 1));
if (first.b < m)
{
Q.push(Node(first.a, min(n, first.b + first.c), max(0, first.c - n + first.b), first.path + 1));
}
}
}
}
if (fuck)cout << "NO" << endl;
}
return 0;
}
##N HDU 2612
注意不能用太暴力的方法，不然会MLE/TLE1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128//一开始的思路是穷举每个点到Y M的距离， TLE
//改进了一下，打表，两次BFS求Y\M到每个点的距离，AC
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 205;
const int dr[] = { -1, 0, 1, 0 };
const int dc[] = { 0, -1, 0, 1 };
int r, c;
int map[maxn][maxn];
int visited[maxn][maxn];
int tot = 0;
int kr[maxn*maxn], kc[maxn*maxn];
int yr, yc, mr, mc;
int yk[maxn*maxn], mk[maxn*maxn];
struct Node
{
int row, col;
int path;
Node() {}
Node(int row, int col, int path) :row(row), col(col), path(path) {}
};
queue<Node> Q;
int main()
{
char chTmp;
while (scanf("%d %d\n", &r, &c) != EOF)
{
memset(map, -1, sizeof(map));
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
cin >> chTmp;
if (chTmp == '.')
{
map[i][j] = 0;
}
else
{
if (chTmp == '@')
{
map[i][j] = ++tot;
kr[tot] = i;
kc[tot] = j;
}
else
{
if (chTmp == 'Y')
{
map[i][j] = 0;
yr = i;
yc = j;
}
else
{
if (chTmp == 'M')
{
map[i][j] = 0;
mr = i;
mc = j;
}
}
}
}
}
getchar();
}
Node temp;
memset(visited, 0, sizeof(visited));
memset(yk, -1, sizeof(yk));
Q.push(Node(yr, yc, 0));
visited[yr][yc] = 1;
while (!Q.empty())
{
temp = Q.front(); Q.pop();
if (map[temp.row][temp.col] > 0)
{
yk[map[temp.row][temp.col]] = temp.path;
}
for (int i = 0; i < 4; i++)
{
if (temp.row + dr[i] < 1 || temp.row + dr[i] > r || temp.col + dc[i] < 1 || temp.col + dc[i] > c)continue;
if (visited[temp.row + dr[i]][temp.col + dc[i]] == 0 && map[temp.row + dr[i]][temp.col + dc[i]] >= 0)
{
visited[temp.row + dr[i]][temp.col + dc[i]] = 1;
Q.push(Node(temp.row + dr[i], temp.col + dc[i], temp.path + 1));
}
}
}
memset(visited, 0, sizeof(visited));
memset(mk, -1, sizeof(mk));
Q.push(Node(mr, mc, 0));
visited[mr][mc] = 1;
while (!Q.empty())
{
temp = Q.front(); Q.pop();
if (map[temp.row][temp.col] > 0)
{
mk[map[temp.row][temp.col]] = temp.path;
}
for (int i = 0; i < 4; i++)
{
if (temp.row + dr[i] < 1 || temp.row + dr[i] > r || temp.col + dc[i] < 1 || temp.col + dc[i] > c)continue;
if (visited[temp.row + dr[i]][temp.col + dc[i]] == 0 && map[temp.row + dr[i]][temp.col + dc[i]] >= 0)
{
visited[temp.row + dr[i]][temp.col + dc[i]] = 1;
Q.push(Node(temp.row + dr[i], temp.col + dc[i], temp.path + 1));
}
}
}
int ans = (1 << 30);
for (int i = 1; i <= tot; i++)
{
if (yk[i] == -1 || mk[i] == -1)continue;
ans = min(ans, yk[i] + mk[i]);
}
printf("%d\n", ans * 11);
}
return 0;
}